Lambda the Ultimate

Just a quick reminder -- the 2008 ICFP Programming Contest starts tomorrow.

Functional Netlists, Sungwoo Park, Jinha Kim, Hyeonseung Im. ICFP 2008.

In efforts to overcome the complexity of the syntax and the lack of formal semantics of conventional hardware description languages, a number of functional hardware description languages have been developed. Like conventional hardware description languages, however, functional hardware description languages eventually convert all source programs into netlists, which describe wire connections in hardware circuits at the lowest level and conceal all high-level descriptions written into source programs.

We develop a variant of the lambda calculus, called l-lambda (linear lambda), which may serve as a high-level substitute for netlists. In order to support higher-order functions, l-lambda uses a linear type system which enforces the linear use of variables of function type. The translation of l-lambda into structural descriptions of hardware circuits is sound and complete in the sense that it maps expressions only to realizable hardware circuits and that every realizable hardware circuit has a corresponding expression in l-lambda. To illustrate the use of l-lambda as a high-level substitute for netlists, we design a simple hardware description language that extends l with polymorphism, and use it to implement a Fast Fourier Transform circuit.

Given the recent discussion about hardware synthesis languages, the appearance of this paper seems timely. The use of linear types is perhaps unsurprising from a technical point of view, but it's surprising when you consider how frequently and in how many different contexts they appear.

Also, one thing I don't understand: there's apparently a difference between a "hardware description language" and a "hardware synthesis language". If anyone could explain what the difference means, I'd appreciate it. :)

See the Dusty Decks announcement.

Non-Deterministic Recursive Ascent Parsing, Renee Leermakers. 1991 conference on European chapter of the Association for Computational Linguistics.

A purely functional implementation of LR-parsers is given, together with a simple correctness proof. It is presented as a generalization of the recursive descent parser. For non-LR grammars the time-complexity of our parser is cubic if the functions that constitute the parser are implemented as memo-functions, i.e. functions that memorize the results of previous invocations. Memo-functions also facilitate a simple way to construct a very compact representation of the parse forest. For LR(0) grammars, our algorithm is closely related to the recursive ascent parsers recently discovered by Kruseman Aretz [1] and Roberts [2]. Extended CF grammars (grammars with regular expressions at the right hand side) can be parsed with a simple modification of the LR-parser for normal CF grammars.

How LR parsers worked always confused me until I learned about their presentation in terms of recursive ascent.

via Jeff Newbern in the discussion forum comes the writeup from the winning entry in the MEMOCODE 2007 contest:

This year, the first MEMOCODE hardware/software codesign contest posed the following problem: optimize matrix-matrix multiplication in such a way that it is split between the FPGA and PowerPC on a Xilinx Virtex IIPro 30. In this paper we discuss our solution, which we implemented on a Xilinx XUP development board with 256 MB of DRAM. The design was done by the five authors over a span of approximately 3 weeks, though of the 15 possible man-weeks, about 9 were actually spent working on this problem. All hardware design was done using Bluespec SystemVerilog (BSV), with the exception of an imported Verilog multiplication unit, necessary only due to the limitations of the Xilinx FPGA toolflow optimizations.

Wow! This is much cooler than the kinds of programs I write :-)

This MIT/Bluespec team won the first contest at MEMOCODE 2007 and the second in MEMOCODE 2008. The results for 2008 are very interesting: The Bluespec team had the highest performance by an order of magnitude, the next fastest program was written by one guy in straight C without using the FPGA, and the rest were mostly in a hybrid of C and (V?)HDL.

Does this make Bluespec the programming tool of choice for discriminating hardware hackers?

Hardware Design and Functional Programming: a Perfect Match by Mary Sheeran, Journal of Universal Computer Science, Special issue devoted to the Brazilian Symposium on Programming Languages, 2005.

This is a slightly odd paper that explains why I am still as fascinated by the combination of functional programming and hardware design as I have ever been. It includes some looking back over my own research and that of others, and contains 60 references. It explains what kinds of research I am doing now, and why, and also presents some neat new results about parallel prefix circuits. It ends by posing lots of hard questions that we need to answer if we are to be able to design and verify circuits successfully in the future.

I was recently invited to be on the panel Reinventing Audio and Music Computation for Many-Core Processors at the International Computer Music Conference (ICMC 2008), Belfast, Ireland, Aug. 2008. In my position statement, The Challenges and Opportunities of Multiple Processors: Why Multi-Core Processors are Easy and Internet is Hard, I explain why programming multi-core processors is basically a sociological problem (the technical problems were solved long ago) and why programming loosely coupled systems (like the Internet) still has a lot of technical challenges. I am curious to hear what the LtU community thinks about this.

Computerworld is undertaking a series of investigations into the most widely-used programming languages.

• Ada - S. Tucker Taft
• Arduino - Tom Igoe
• ASP.NET - Microsoft
• AWK - Alfred V. Aho
• AWK - Brian Kernighan
• Bash - Chet Ramey
• Bourne Shell - Steve Bourne
• C# - Anders Hejlsberg
• C++ - Bjarne Stroustrup
• Clojure - Rich Hickey
• ColdFusion - Jeremy Allaire
• D - Walter Bright
• Erlang - Joe Armstrong
• F# - Don Syme
• Falcon - Giancarlo Niccolai
• Forth - Charles Moore
• Groovy - Guillaume Laforge
• Haskell - Simon Peyton Jones
• INTERCAL - Don Wood
• JavaScript - Brendan Eich
• Lua - Roberto Ierusalimschy
• MATLAB - Cleve Moler
• Modula-3 - Luca Cardelli
• Objective C - Brad Cox
• Perl - Larry Wall
• Python - Guido van Rossum
• Scala - Martin Odersky
• Tcl- John Ousterhout
• YACC - Stephen C. Johnson

Thanks to French public funds, the next generation of Free Software code coverage tools is on its way. Project Coverage will produce a Free Software coverage analysis toolset together with the ability to generate artifacts that allow the tools to be used for safety-critical software projects undergoing a DO-178B software audit process for all levels of criticality...

The key insight of “Project Coverage” is as follows: code coverage can greatly benefit from recent advances in hardware virtualization technology as promoted, for instance, by QEMU.

Revisiting Coroutines, by Ana Lucia de Moura and Roberto Ierusalimschy:

This paper defends the revival of coroutines as a general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and oneshot partial continuations. We also show that full asymmetric coroutines and one-shot partial continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, specially in the realm of procedural languages. Finally, we provide a collection of programming examples that illustrate the use of full asymmetric coroutines to support direct and concise implementations of several useful control behaviors, including cooperative multitasking.

Coroutines seem to get fairly short riff in the literature, and they have only been discussed on LTU, a couple of times. Given coroutines have such a straightforward mapping to hardware, I hope they get more attention.

Coroutines show up in many different places. For instance, the inter-process communication (IPC) facilities of microkernels, like EROS, are a faithful implementation of asymmetric coroutines, with an important difference. Essentially, yield and resume must both take an explicit coroutine argument naming the coroutine respectively yield to and resume. If the coroutine to yield to is left implicit, as it is in most treatments I've seen, then coroutines become less composable since yield returns control to the innermost resume which, given abstract types, might be the wrong one.

This problem is discussed in Section 5.6, "Avoiding Interference Between Control Actions". The paper recommends tagging coroutines to match up resume/yield pairs, but the EROS IPC system provides a more direct encoding via a "resume" capability, which is a single-use coroutine used to return control directly to a client. Each subsequent invocation of the object synthesizes a new resume capability.

Taking this to the extreme implies that yield and resume can be unified into a single "invoke" operation which accepts a coroutine argument to be used in a subsequent invoke operation. Indeed, these are "symmetric coroutines". This paper suggests that symmetric coroutines are harder to understand due to the actors/CPS-like nature of the control flow.